/*
    http://bhepple.freeshell.org

    Copyright (C) 2010 Bob Hepple <bhepple@freeshell.org>

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; see the file COPYING.  If not, write to
    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
    Boston, MA 02111-1307, USA.

*/

/**
 * \file tba.c
 */

#include <stdarg.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <tba.h>

typedef struct tba_phys_s {
    /** maximum number of array elements */
    size_t maxlen;
    /** current length of the array as set by tba_put_index() */
    size_t curlen;
    /** size of array elements (0 for variable) */
    size_t width;
    /** callbacks for payload referents (for managed payloads only). */
    tba_free_callback_t free_callback;
    tba_create_callback_t create_callback;
    tba_copy_callback_t copy_callback;
    void *caller_data;
    /** physical storage for array - will be expanded as needed */
    tba array; /* >= 2 pointers - 1 data + a NULL terminator */
} *tba_phys;

static int tba_chunksize = 128;

#define OFFSET (sizeof(struct tba_phys_s) - sizeof(tba))

size_t sizeof_tba(size_t maxlen)
{
    return(sizeof(struct tba_phys_s) + (maxlen + 1) * sizeof(tba));
}

static size_t array_capacity(size_t physize)
{
    return(((physize - sizeof(struct tba_phys_s)) / sizeof(tba)) - 1);
}

#define check_tba(s_in) ((tba_phys) ((void *)(s_in) - OFFSET))

void tba_set_chunksize(size_t chunksize)
{
    
    if ((int)chunksize > 0) tba_chunksize = sizeof(void *) * (1 + (chunksize - 1) / sizeof(void *));
}

tba tba_push_str(tba *dest_in, const char * string)
{
    tba retval = NULL;
    char * new_string = xmalloc(strlen(string) + 1);
    strcpy(new_string, string);
    retval = tba_push(dest_in, new_string);
    return(retval);
}

tba tba_new(size_t                maxlen_in_raw, 
            size_t                width,
            tba_free_callback_t   free_callback,
            tba_create_callback_t create_callback,
            tba_copy_callback_t   copy_callback, 
            void *                caller_data)
{
    tba retval = NULL;
    tba_phys retval_phys = NULL;
    int maxlen_in = maxlen_in_raw;
    int maxlen = maxlen_in;
    size_t physize = 0;
    int i = 0;
    if ((int)maxlen_in_raw <= 0) {
        maxlen_in = 0;
    }
    maxlen = maxlen_in;

    physize = 1 + (sizeof_tba(maxlen) - 1) / tba_chunksize;
    physize *= tba_chunksize;
    maxlen = array_capacity(physize);

    if ( !(retval_phys = (tba_phys) xcalloc(1, physize)) ) goto end;

    retval = (tba) ((void *)retval_phys + OFFSET);
    retval_phys->width = ((int)width > 0? width: 0);
    for (i = 0; i < maxlen_in; i++) {
        if ((retval[i] == NULL) && (retval_phys->width > 0)) {
            if ( !(retval[i] = xcalloc(1, retval_phys->width)) ) goto hell;
        }
        if (create_callback) {
            void *p;

            p = (*create_callback)(retval[i], i, caller_data);
            if (!p) goto hell;
            retval[i] = p;
        }                    
    }
            
    retval_phys->maxlen = maxlen;
    retval_phys->curlen = -1;
    if (retval_phys->width > 0) retval_phys->curlen = maxlen_in;
    retval_phys->free_callback = free_callback;
    retval_phys->create_callback = create_callback;
    retval_phys->copy_callback = copy_callback;
    retval_phys->caller_data = caller_data;
    goto end;

hell:
    {
        int j = 0;

        for (j = 0; j < i; j++) {
            if (retval[j]) {
                if (free_callback) retval[j] = (*free_callback)(retval[j], j,
                                                                caller_data);
                if (retval[j]) xfree(retval[j]);
                retval[j] = NULL;
            }
        }
        xfree(retval_phys);
        retval_phys = NULL;
        retval = NULL;
        goto end;
    }

end:
    return(retval);
}

void tba_free(tba *s_in)
{
    tba_phys s_phys = NULL;
    int i = 0;

    if (s_in && *s_in) {
        if ( (s_phys = check_tba(*s_in)) ) {
            for (i = 0; i < s_phys->maxlen; i++) {
                tba a = (*s_in)[i];
                if (a) {
                    if (s_phys->free_callback) {
                        a = (*(s_phys->free_callback))(a, i, 
                                                       s_phys->caller_data);
                    }
                    if (a && s_phys->width > 0) {
                        xfree(a);
                    }   
                    (*s_in)[i] = NULL;
                }
            }
            xfree(s_phys);
            *s_in = NULL;
        }
    }
}

int tba_get_maxlen(tba s_in)
{
    int retval = 0;
    
    if (s_in) {
        tba_phys s = check_tba(s_in);
        if (s) {
            retval = s->maxlen;
        } else {
            retval = -1;
        }
    }
    return(retval);
}

/* by-pass check_tba for an already-checked array: */
static int get_len(tba_phys array_phys, tba array)
{
    int retval;

    if (array_phys->curlen != -1) {
        retval = array_phys->curlen;
    } else {
        for (retval = array_phys->maxlen; 
             retval && !array[retval - 1]; 
             retval--) ;
        array_phys->curlen = retval;
    }
    return(retval);
}

int tba_get_len(tba array)
{
    int retval = -1;
    tba_phys array_phys = NULL;
    
    if (array) {
        array_phys = check_tba(array);
        if (array_phys) retval = get_len(array_phys, array);
    }
    return(retval);
}

tba tba_put_index(tba *dest, size_t num, void *value)
{
    tba retval = NULL;
    tba_phys retval_phys = NULL;
    int oldlen;

    if (!dest || ((int)num < 0)) goto end;
    if (*dest) {
        retval = *dest;
    } else {
        /* create a minimalist array */
        retval = tba_new(num + 1, 0, NULL, NULL, NULL, NULL);
    }

    if ( !(retval_phys = check_tba(retval)) ) {
        retval = NULL;
        goto end;
    }

    oldlen = get_len(retval_phys, retval);
    if (num >= oldlen) {
        if (value == NULL) {
            /* we're done */
            goto end;
        } else {
            /* expand the array - if width or create_callback is set, then
             * this will also populate the intervening items. */
            if ( !(retval = tba_resize(&retval, num + 1)) ) goto end;
            if ( !(retval_phys = check_tba(retval)) ) {
                retval = NULL;
                goto end;
            }
        }
    }

    if (retval[num]) {
        /* free the old one */
        if (retval_phys->free_callback) {
            retval[num] = (*(retval_phys->free_callback))(retval[num], 
                                                          num,
                                                          retval_phys->caller_data);
        }
        if (retval[num] && (retval_phys->width > 0)) {
            xfree(retval[num]);
            retval[num] = NULL;
        }
    }

    retval[num] = value;
    if (num + 1 > (int)retval_phys->curlen) retval_phys->curlen = num + 1;

end:
    if (retval && dest) *dest = retval;

    return(retval);
}

void *tba_get_index(const tba source, size_t num)
{
    void *retval = NULL;
    tba_phys source_phys = NULL;
    int len = 0;

    if (!source || ((int)num < 0)) goto end;
    if ( !(source_phys = check_tba(source)) ) goto end;
    len = get_len(source_phys, source);
    if (num > len) goto end;
    retval = source[num];

end:
    return(retval);
}

tba tba_resize(tba *dest, size_t newlen_in)
{
    tba retval = NULL;
    tba_phys retval_phys = NULL;
    size_t oldmaxlen = 0;
    size_t oldlen = 0;
    size_t newmaxlen = newlen_in;
    size_t physize = 0;
    int i = 0;
    if ( !(dest && ((int)newlen_in > 0)) ) {
        goto end;
    }
    if (!*dest) {
        retval = tba_new(newlen_in, 0, NULL, NULL, NULL, NULL);
        goto end;
    }

    if ((retval_phys = check_tba(*dest)) == NULL) goto end;

    retval = *dest;
    oldmaxlen = retval_phys->maxlen;

    oldlen = get_len(retval_phys, *dest);
 
    physize = 1 + (sizeof_tba(newlen_in) - 1) / tba_chunksize;
    physize *= tba_chunksize;
    newmaxlen = array_capacity(physize); /* >= newlen_in */

    if ((newmaxlen == oldmaxlen) && (newlen_in == oldlen)) {
        retval = NULL;
        goto end;
    }

    /* for a reduction, free any truncated members: */
    for (i = newlen_in; i < oldmaxlen; i++) {
        if (retval[i]) {
            if (retval_phys->free_callback) {
                retval[i] = (*(retval_phys->free_callback))(retval[i], 
                                                            i, 
                                                            retval_phys->caller_data);
            }
            if (retval[i] && (retval_phys->width > 0)) {
                xfree(retval[i]);
                retval[i] = NULL;
            }
        }
        retval_phys->curlen = newlen_in;
    }

    if ( !(retval_phys = xrealloc(retval_phys, physize)) ) {
        /* _can_ this fail if it's a reduction?? */
        retval = NULL;
        goto end;
    }

    retval_phys->maxlen = newmaxlen;
    /* for a reduction, is it likely to have been moved? man page is
     * silent on the topic, so let's be safe */
    retval = (tba) ((void *)retval_phys + OFFSET);
            
    /* for an expansion, zero the new members: */
    for (i = oldlen; i <= newmaxlen; i++) retval[i] = NULL;

    /* for an expansion, create new members: */
    for (i = oldlen; i < newlen_in; i++) {
        if ((retval[i] == NULL) && (retval_phys->width > 0)) {
            if ( !(retval[i] = xcalloc(1, retval_phys->width)) ) goto hell;
            retval_phys->curlen = i;
        }
        if (retval_phys->create_callback) {
            void *p;

            p = (*retval_phys->create_callback)(retval[i], i, 
                                                retval_phys->caller_data);
            if (!p) goto hell;
            retval[i] = p;
            retval_phys->curlen = i;
        }
    }
    retval[newlen_in] = NULL;
    goto end;
    
hell:
    {
        int j;
                
        /* undo what we've done so far ... */
        for (j = oldmaxlen; j < i; j++) {
            xfree(retval[j]);
            retval[j] = NULL;
        }
        if (dest) *dest = retval; /* has been re-alloc'd */
        retval = NULL;
        goto end;
    }

end:
    if (retval && dest) *dest = retval;
    return(retval);
}

tba tba_insert(tba *dest, size_t pos_in, size_t num)
{
    tba retval = NULL;
    tba_phys dest_phys = NULL;
    tba new_array = NULL;
    tba_phys new_array_phys = NULL;
    size_t pos = pos_in;
    size_t oldmaxlen = 0;
    size_t oldlen = 0;
    int i = 0;

    if ( !(dest && *dest && ((int)num > 0)) ) goto end;

    if ( !(dest_phys = check_tba(*dest)) ) goto end;
    oldmaxlen = dest_phys->maxlen;
    oldlen = get_len(dest_phys, *dest);
    if ((pos > oldlen) || ((int)pos < 0)) pos = oldlen;

    if (oldlen + num < oldmaxlen) {
        /* just move right segment to the end */
        new_array = *dest;
        new_array_phys = dest_phys;
    } else {    
        if ( !(new_array = tba_new(oldlen + num, 0, NULL, NULL, NULL, 
                                       NULL)) ) {
            goto end;
        }
        new_array_phys = (tba_phys)((void *)new_array - OFFSET);
        /* copy left section */
        for (i = 0; i < pos; i++) new_array[i] = (*dest)[i];
    }

    /* copy right section */
    for (i = oldlen; (i >= 0) && (i >= pos); i--) {
        new_array[i + num] = (*dest)[i];
        new_array[i] = NULL;
    }
    new_array_phys->curlen = oldlen + num;
    /* zero blank space at end */
    for (i = oldlen + num; i < new_array_phys->maxlen; i++) new_array[i] = NULL;

    /* create new payloads */
    for (i = pos; i < pos + num; i++) {
        if ((new_array[i] == NULL) && (dest_phys->width > 0)) {
            if ( !(new_array[i] = xcalloc(1, dest_phys->width)) ) goto hell;
        }
        if (dest_phys->create_callback) {
            void *p;

            p = (*(dest_phys->create_callback))(new_array[i], i, 
                                                dest_phys->caller_data);
            if (!p) goto hell;
            new_array[i] = p;
        }  
    }

    if (new_array_phys != dest_phys) {
        new_array_phys->width = dest_phys->width;
        new_array_phys->free_callback = dest_phys->free_callback;
        new_array_phys->create_callback = dest_phys->create_callback;
        new_array_phys->copy_callback = dest_phys->copy_callback;
        new_array_phys->caller_data = dest_phys->caller_data;
        xfree(dest_phys);
    }
    retval = new_array;
    goto end;

hell: /* free whatever has been created */
    {
        for (i = pos; i < pos + num; i++) {
            if (new_array[i]) {
                if (new_array_phys->free_callback) {
                    new_array[i] = (*(new_array_phys->free_callback))(new_array[i], i, new_array_phys->caller_data);
                }
                if (new_array[i]) xfree(new_array[i]);
            }
            new_array[i] = NULL;
        }
        /* undo in-place copy where the original array was big enough */
        if (new_array_phys == dest_phys) {
            for (i = pos; i < oldlen; i++) {
                new_array[i] = (*dest)[i + num];
                (*dest)[i + num] = NULL;
            }
            new_array[oldlen] = NULL;
        } else {
            if (new_array_phys) xfree(new_array_phys);
        }
        retval = NULL;
        goto end;
    }

end:
    if (retval && dest) *dest = retval;
    return(retval);
}

tba tba_delete(tba dest, size_t pos_in, size_t num_in)
{
    size_t oldmaxlen = 0;
    size_t oldlen = 0;
    size_t pos = pos_in;
    size_t num = num_in;
    tba retval = NULL;
    tba_phys dest_phys = NULL;
    int i = 0;

    if (!dest) goto end;

    if ( !(dest_phys = check_tba(dest)) ) goto end;
    oldmaxlen = dest_phys->maxlen;
    oldlen = get_len(dest_phys, dest);

    if ((oldmaxlen <= 0) || (oldlen <= 0)) goto end;
    if (oldlen > oldmaxlen) goto end;

    if ((int)pos == -1) {
        /* delete last */
        pos = oldlen - 1;
    } else if ( !(((int)pos >= 0) && (pos < oldlen)) ) {
        goto end;
    }

    if (pos + num > oldlen) num = oldlen - pos;
    if ((int) num <= 0) goto end;

    for (i = pos; i < pos + num; i++) {
        tba a = dest[i];
        if (a) {
            if (dest_phys->free_callback) {
                a = (*(dest_phys->free_callback))(a, i, dest_phys->caller_data);
            }
            if (a && (dest_phys->width > 0)) xfree(a);
            dest[i] = NULL;
        }
    }
    if (dest_phys->curlen != -1) dest_phys->curlen = oldlen - num;

    /* move remainder left */
    for (i = pos; i < oldlen - num; i++) dest[i] = dest[i + num];
    for (i = oldlen - num; i <= oldmaxlen; i++) dest[i] = NULL;
    retval = dest;

end:
    return(retval);
}

tba tba_copy(const tba source)
{
    tba retval = NULL;
    tba_phys retval_phys = NULL;
    tba_phys source_phys = NULL;
    int i = 0;
    int j = 0;
    size_t oldlen = 0;

    if (!source) goto end;

    if ( !(source_phys = check_tba(source)) ) goto end;
    oldlen = get_len(source_phys, source);

    retval = tba_new(oldlen, source_phys->width, NULL, NULL, NULL, NULL);
    if (retval == NULL) goto end;
    retval_phys = check_tba(retval);
    retval_phys->free_callback = source_phys->free_callback;
    retval_phys->create_callback = source_phys->create_callback;
    retval_phys->copy_callback = source_phys->copy_callback;
    retval_phys->caller_data = source_phys->caller_data;
    retval_phys->curlen = source_phys->curlen;

    for (i = 0; i < oldlen; i++) {
        if (source[i] == NULL) {
            if (retval[i]) xfree(retval[i]);
            retval[i] = NULL;
            continue;
        } 
        if (source_phys->width > 0) {
            memcpy(retval[i], source[i], source_phys->width);
        }
        if (source_phys->copy_callback) {
            void *p;
            
            p = (*(source_phys->copy_callback))(retval[i], source[i], i,
                                                source_phys->caller_data);
            if (!p) goto hell;
            retval[i] = p;
        }
    }
    goto end;

hell:
    if (retval_phys->width > 0) i = oldlen;

    for (j = 0; j < i; j++) {
        if (retval[j]) {
            if (source_phys->free_callback) {
                retval[j] = (*(source_phys->free_callback))(retval[j], j, 
                                                            source_phys->caller_data);
            }
            if (retval[j]) xfree(retval[j]);
        }
        retval[j] = NULL;
    }
    xfree(retval_phys);
    retval = NULL;

end:
    return(retval);
}

tba tba_cat(tba *dest, tba source)
{
    tba retval = NULL;
    tba_phys dest_phys = NULL;
    size_t destmaxlen = 0;
    size_t destlen = 0;
    tba_phys source_phys = NULL;
    size_t sourcelen = 0;
    size_t newlen = 0;
    int i = 0;

    if ( !(dest && source) ) goto end;

    if (*dest == NULL) {
        retval = tba_copy(source);
        goto end;
    }

    if ( !(source_phys = check_tba(source)) ) goto end;
    if ( !(dest_phys = check_tba(*dest)) ) goto end;

    if (dest_phys->width != source_phys->width) goto end;

    sourcelen = get_len(source_phys, source);

    retval = *dest;
    destmaxlen = dest_phys->maxlen;

    destlen = get_len(dest_phys, *dest);

    newlen = destlen + sourcelen;
    if (destmaxlen < newlen) {
        int dup_self = 0;

        if (source == *dest) {
            dup_self = 1;
        }
        /* this resize would create new elements and trigger the dest
         * create_callback - so set width to 0 and callback to NULL
         * for now: also, free_callback could be called in a 'hell' */
        tba_create_callback_t save_create_callback = 
            dest_phys->create_callback;
        tba_free_callback_t save_free_callback = 
            dest_phys->free_callback;
        size_t save_width = dest_phys->width;
        dest_phys->create_callback = NULL;
        dest_phys->free_callback = NULL;
        dest_phys->width = 0;
        retval = tba_resize(dest, newlen);
        if ( !(dest_phys = check_tba(*dest)) ) goto end;
        dest_phys->create_callback = save_create_callback;
        dest_phys->free_callback = save_free_callback;
        dest_phys->width = save_width;
        if (!retval) goto end;
        if (dup_self) {
            source = retval;
            source_phys = dest_phys;
        }
    }

    /* copy the elements into place: */
    for (i = 0; i < sourcelen; i++) {
        if (source[i]) {
            if (source[i] == NULL) {
                retval[i + destlen] = NULL;
                continue;
            }

            if ((retval[i + destlen] == NULL) && (dest_phys->width > 0)) {
                if ( !(retval[i + destlen] = xcalloc(1, dest_phys->width)) ) {
                    goto hell;
                }
                memcpy(retval[i + destlen], source[i], source_phys->width);
            }

            if (dest_phys->copy_callback) {
                void *p;
            
                p = (*(dest_phys->copy_callback))(retval[i + destlen], 
                                                  source[i], 
                                                  i + destlen,
                                                  dest_phys->caller_data);
                if (!p) goto hell;
                retval[i + destlen] = p;
            }
        }
    }
    dest_phys->curlen += sourcelen;
    goto end;

hell:
    {
        int j;

        /* undo partially completed copy */
        for (j = destlen; j < i + destlen; j++) {
            if (retval[j]) {
                if (dest_phys->free_callback) {
                    retval[j] = (*(dest_phys->free_callback))(retval[j], j + destlen, dest_phys->caller_data);
                    if (retval[j]) xfree(retval[j]);
                }
            }
            retval[j] = NULL;
        }
    }

end:
    if (retval && dest) *dest = retval;
    return(retval);
}
    
tba tba_push(tba *stack, void *item)
{
    tba_phys stack_phys = NULL;
    tba retval = NULL;
    int len = 0;

    if (stack) retval = *stack;
    if (retval == NULL) {
        if ( !(retval = tba_new(1, 0, NULL, NULL, NULL, NULL)) ) goto end;
        if ( !(stack_phys = check_tba(retval)) ) {
            retval = NULL;
            goto end;
        }
        stack_phys->curlen = 1;
    } else {
        if ( !(stack_phys = check_tba(retval)) ) {
            retval = NULL;
            goto end;
        }
        len = get_len(stack_phys, retval);
        if (len == stack_phys->maxlen) {
            /* this resize would create new elements and trigger the dest
             * create_callback - so set width to 0 and callback to NULL
             * for now: also, free_callback could be called in a 'hell' */
            tba_create_callback_t save_create_callback = NULL;
            tba_free_callback_t save_free_callback = NULL;

            save_create_callback = stack_phys->create_callback;
            save_free_callback = stack_phys->free_callback;
            size_t save_width = stack_phys->width;
            stack_phys->create_callback = NULL;
            stack_phys->free_callback = NULL;
            stack_phys->width = 0;

            if ( !(retval = tba_insert(&retval, -1, 1)) ) goto end;
            if ( !(stack_phys = check_tba(retval)) ) {
                retval = NULL;
                goto end;
            }

            stack_phys->create_callback = save_create_callback;
            stack_phys->free_callback = save_free_callback;
            stack_phys->width = save_width;
        } else {
            stack_phys->curlen++;
        }
    }
    /* we've now got at least one spare slot at 'len' */
    retval[len] = item;
    retval[len + 1] = NULL;

end:
    if (retval && stack) *stack = retval;
    return(retval);
}

void *tba_get_last(const tba stack)
{
    void *retval = NULL;
    tba_phys stack_phys = NULL;
    int len = 0;

    if ( (stack_phys = check_tba(stack)) ) {
        len = get_len(stack_phys, stack);
        if (len) retval = stack[len - 1];
    }

    return(retval);
}

void *tba_get_first(const tba stack)
{
    void *retval = NULL;
    tba_phys stack_phys = NULL;

    if ( (stack_phys = check_tba(stack)) ) retval = stack[0];

    return(retval);
}

void *tba_pop_last(tba stack)
{
    tba retval = NULL;
    tba_phys stack_phys = NULL;
    int len = 0;

    if ( (stack_phys = check_tba(stack)) ) {
        len = get_len(stack_phys, stack);
        if (len) {
            retval = stack[len - 1];
            stack[len - 1] = NULL;
            if (stack_phys->curlen != -1) stack_phys->curlen--;
        }
    }
    return(retval);
}

void *tba_pop_first(tba stack)
{
    void *retval = NULL;
    tba_phys stack_phys = NULL;
    int i = 0;
    int len = 0;

    if ( (stack_phys = check_tba(stack)) ) {
        retval = stack[0];
        len = get_len(stack_phys, stack);
        for (i = 0; i < len; i++) stack[i] = stack[i + 1];
        stack[i] = NULL;
        if (stack_phys->curlen != -1) stack_phys->curlen--;
    }
    return(retval);
}


